package JackSu.aobing;

import java.util.ArrayList;

/**
 * Heap
 *
 * @author Syzer
 * @Description 自己写的堆
 * @Date 2021/7/22 9:46
 */
public class Heap {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        int len = input.length;
        ArrayList<Integer> list = new ArrayList<>();
        int[] heap = new int[k];
        for(int i = 0;i < len;i++) {
            if(i < k) {
                heap[i] = input[i];
                siftUp(heap, i, input[i]);
            } else {
                if(heap[0] > input[i]) {
                    heap[0] = input[i];
                    siftDown(heap, 0, input[i]);
                }
            }
        }
        for(int i = 0;i < k;i++) {
            list.add(heap[i]);
        }
        return list;
    }

    // 每个根节点的数都小于它的左右节点，左2*n+1，右2*n+2
    private void siftDown(int[] arr, int i, int val) {
        // 交换的长度不超过数组长度的一半
        int len = arr.length;
        int half = len >>> 1;
        while(i < half) {
            // 假设左节点为最大值
            int maxIndex = (i << 1) + 1;
            int maxValue = arr[maxIndex];
            // 与右节点比较
            int rightIndex = maxIndex + 1;
            if(rightIndex < len && arr[rightIndex] > maxValue) {
                maxValue = arr[maxIndex = rightIndex];
            }
            // 与根节点比较，根节点大或等于直接结束
            if(val >= maxValue) {
                break;
            }
            // 根节点小则交换位置，i取新位置，下一次继续比较
//             swap(arr, i, maxIndex);
            arr[i] = maxValue;
            i = maxIndex;
        }
        arr[i] = val;
    }

    private void siftUp(int[] arr, int i, int val) {
        while(i > 0) {
            int parentIndex = (i - 1) >>> 1;
            if(val <= arr[parentIndex]) {
                break;
            }
            arr[i] = arr[parentIndex];
            i = parentIndex;
        }
        arr[i] = val;
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        Heap heap = new Heap();
        ArrayList<Integer> list = heap.GetLeastNumbers_Solution(new int[]{4, 5, 1, 6, 2, 7, 3, 8}, 4);
        System.out.println(list.toString());
    }
}
